Rural areas in emerging countries and rural areas in general have low penetration of network services, e.g., Internet and cell phone services. In emerging countries, traditional networking and telecommunication services may be too expensive for the average person and/or family. In rural areas, there may not be sufficient interest from potential users to justify the expense in investing in traditional networking and telecommunication infrastructures. Accordingly, the deployment of traditional networking and telecommunication technologies may be prohibitively expensive in these areas.
Recently, IEEE 802.11 WiFi equipment based mesh networks have been proposed as a feasible solution to meet the requirements for rural networks. WiFi equipment is highly commoditized, widely available and inexpensive. In addition, WiFi equipment provides broadband speeds. Directional antenna equipment may send an 802.11 signal over tens of kilometers. Hence, the use of WiFi equipment and directional antenna equipment may be used to span required distances to connect rural areas. IEEE 802.11b equipment offers a peak rate of 11 Mbps, while 802.11g can support up to 54 Mbps.
FIG. 1 illustrates a mesh network 1. For explanation purposes, each node 10 in the rural mesh network may be considered as a town or a village. At least one of the town or village may be a gateway node 20. The gateway node 20 may be connected to the Internet or a telecommunication service provider in a tradition manner. The gateway node 20 may be entry and exit points for all traffic in the mesh network 1.
As illustrated in FIG. 1, the nodes 10 may be connected to each other through point-to-point wireless links using IEEE 802.11 equipment. IEEE 802.11 provides several non-interfering channels for communication, each of the 802.11b and g variants has 3 channels, and the 802.11a variant has 12 channels. Some nodes 10 may connect directly to the gateway node 20, and other nodes 10 may connect to the gateway node 20 through one or more hops in the mesh network 1. The distance between the nodes 10 may be in the order of 10-15 km. In order for a signal to traverse this distance, high-gain directional antennas may be used at the end-points of a link. The high-gain directional antennas may be mounted on towers to establish a line of sight with other high-gain directional antennas.
While directional antennae are designed to transmit and receive in a specific direction, the directionality of the signals become more effective at distances further away from the sending point, which is known as the near field effect. Due to the near field effect, adjacent links at a node 10 may interfere with each other in certain communication modes.
As illustrated in FIG. 2, at any one of the nodes 10, simultaneous transmission (Tx) and reception (Rx) on the same channel is not possible, because the transmission will interfere with the reception and vice versa. This is known as Mix-Rx-Tx interference. To avoid the Mix-Rx-Tx interference, while keeping a set of links active on the same channel, requires that a constraint be imposed on the set of active links. Roughly stated the network is conceptually divided into two sub-networks such that links exist between nodes in different sub-networks but not between node in a same subnetwork.
The constraint is stated more precisely using the language of mathematical graph theory. A mesh network having nodes interconnected by links may be represented by a graph. In the context of graph theory, another name for a node is a vertex. A connection between two nodes (or vertices) is referred to as an edge (or link as used above). In the language of graph theory, the constraint referred to above is the graph indicated by active links is bi-partite. A bi-partite graph may be defined as a set of graph vertices decomposed into two disjoint sets such that no two graphs vertices within the same set are adjacent (i.e., connected). For example and with reference to FIG. 3, assume there are nodes u, v, w and x in a mesh network. The mesh network may be represented by a graph G. The nodes may be partitioned into two subsets B1={u, v} and B2={w, x}. To avoid Mix-Rx-Tx interference, the graph G should be bi-partite. For example, no nodes in subset B1 may be connected to each other. However, a node in subset B1 may be connected to one or more nodes in subset B2. As stated above, a connection between two (2) nodes is known as an edge or link.
Consider a subgraph of a mesh graph that is induced by active links at a given instant. To avoid Mix-Rx-Tx interference, every node must be either transmitting on all incident links or receiving on all incident links. In other words, no two transmitting nodes (and no two receiving nodes) may be neighbors (i.e., connected). It follows that, no two nodes may transmit to each other (and receive from each other) at the same time. Therefore, the subgraph is bi-partite.
Although Mix-Rx-Tx interference prevents simultaneous Tx and Rx at a node 20, a node 20 may synchronously transmit (or synchronously receive) on all incident links. This is called a SynTx (or SynRx). The SynTx/SynRx is known as a SynOp: synchronous operation of links at a node.
In the conventional art, a 2-Phase (2-P) medium access control (MAC) protocol based on SynOp has been proposed. The protocol operates on a bi-partite graph by switching each node between two phases: SynRx and SynTx. With reference to FIG. 3, let B1 and B2 be the two independent sets of nodes in a bi-partite graph. To start its transmission, a node v in B1 waits for all neighbors in B2 to complete their transmissions. Then, v transmits to all neighbors in B2. (The algorithm for a node in B2 is symmetric.) In other words, when a node switches from SynRx to SynTx, its neighbors switch from SynTx to SynRx, and vice versa.
Given a single channel, the 2P protocol is restricted to operate only on a bi-partite graph. However, if multiple (non-interfering) channels are available, the 2P protocol may operate on multiple bi-partite graphs using a different channel for each bi-partite graph.
The 2P protocol has a constraint on the fraction of time links are active in a given direction. For example, for the 2P algorithm on a bi-partite subgraph (two independent sets B1 and B2) and operating on a single channel, a link is always active in one direction or the other. Then the fraction of time a link is active in a given direction (from B1 to B2) must be identical for all links. Otherwise, if any two links are active for different fractions of time from B1 to B2, then, as every link is always active in one direction or the other, this difference in fractions propagates through the graph; and gives rise to different fractions at some pair of adjacent links. However, as illustrated in FIG. 3, different fractions at two adjacent links cause Mix-Rx-Tx interference at the common node.
Accordingly, in the P2 protocol all links within a bi-partite subgraph (on the same channel) should be active for the same fraction of time in either direction. If several channels are available, and the given network graph is partitioned into bi-partite subgraphs, then, the 2P protocol may run on a separate channel on each bi-partite subgraph, and different subgraphs can have different fractions.